package com.company.ljh.easy;

import com.company.ljh.utils.TreeNode;

public class 二叉树直径 {
    /**
     * 思路：直径的值为每一个节点左子树深度+右子树深度的最大值
     * 因此使用递归求左右子树深度，并顺便记录当前节点的左子树深度+右子树深度的最大值
     */
    private int maxSize = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getDepth(root);
        int result = maxSize;
        maxSize = 0;
        return result;
    }
    public int getDepth(TreeNode root){
        if (root == null){
            return 0;
        }
        //获取左子树深度
        int left  = getDepth(root.left);
        //获取右子树深度
        int right = getDepth(root.right);
        //获取当前节点的直径
        if (maxSize < (left+right)){
            maxSize = left+right;
        }
        return Math.max(left,right)+1;
    }
}
